#ifndef _TORUS_HH_
#define _TORUS_HH_
#include "Bug.h"
#include "FastSet.hh"
#include <cmath>
#include <sstream>
#include <iomanip>

typedef unsigned uLocation;


extern FastSet<unsigned> visited;
extern FastSet<unsigned> visited2;


/// Torus properties
struct Torus
{
  unsigned rows;
  unsigned cols; 
  unsigned size;

  // precomputed (N,E,S,W,null) directions
  static const unsigned TDIRECTIONS = 4;
  static const unsigned ALLDIRECTIONS = TDIRECTIONS+1;
  uLocation * direction_map;

  /// Class builder
  Torus() :
    rows(0), cols(0), size(0), direction_map(NULL)
  {
  }

  /// Class killer
  ~Torus()
  {
    if(direction_map!=NULL)
      delete [] direction_map;
  }

  /// Initializer
  void init(unsigned _rows, unsigned _cols) 
  {
    TRACK();
    
    rows = _rows;
    cols = _cols;
    size = rows*cols;

    visited.init(size);
    visited2.init(size);



    init_direction_map();
  }


  /// conversion (row,col) -> uLocation
  inline uLocation to_uLocation(int row, int col) const
  {
    return row*cols+col;
  }
  
  /// conversion uLocation -> row
  inline unsigned get_row(uLocation loc) const
  {
    if (cols)
      return loc / cols;
    else
      return 0;
  }
  
  /// conversion uLocation -> col
  inline unsigned get_col(uLocation loc) const
  {
    if (cols)
      return loc % cols;
    else
      return 0;
  }


 
  /// fast direction computation scheme
  inline uLocation getLocation(uLocation loc, unsigned direction) const
  {
    ASSERT(direction_map!=NULL);
    ASSERT(loc < size);
    ASSERT(direction < TDIRECTIONS+1);
    
    return direction_map[loc*ALLDIRECTIONS+direction];
  }
  

  /// direction computation scheme
  inline unsigned getDirection(uLocation from, uLocation to) const
  {
    unsigned d = 0;
    while(d<ALLDIRECTIONS)
      {
	if(getLocation(from,d)==to) break; 
	d++;
      }
    return d;
  }
  


  /// slow direction computation scheme
  /// used only for initialization
  uLocation slow_getLocation(uLocation loc, unsigned direction)
  {
    const int ALLDIRS[5][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1}, {0, 0} };//{N, E, S, W, null }
    signed row = (loc / cols + rows + ALLDIRS[direction][0]) % rows;
    signed col = (loc % cols + cols + ALLDIRS[direction][1]) % cols;
    
    return to_uLocation(row,col);
  }


  ///returns the euclidean distance between two locations with the edges wrapped
  double distance(uLocation loc1, uLocation loc2)
  {
    int row1 = loc1 / cols,
      col1 = loc1 % cols,
      row2 = loc2 / cols,
      col2 = loc2 % cols;
    int d1 = (row1 >= row2)?(row1-row2):(row2-row1),
      d2 = (col1 >= col2)?(col1-col2):(col2-col1),
      dr = std::min<int>(d1, rows-d1),
      dc = std::min<int>(d2, cols-d2);
    return sqrt(dr*dr + dc*dc);
  }


  /// init direction map
  void init_direction_map(void)
  {
    TRACK();
    
    ASSERT(direction_map == NULL);
    direction_map = new uLocation[size*ALLDIRECTIONS];

    for(uLocation loc = 0; loc!=size; ++loc)
      for(unsigned d=0; d!=ALLDIRECTIONS; ++d)
	direction_map[loc*ALLDIRECTIONS+d] = slow_getLocation(loc,d);
  }


  /// char output
  char direction_name(unsigned direction)
  {
    static const char CDIRECTIONS[6] = {'N', 'E', 'S', 'W', '-', '?'};
    ASSERT(direction<6);

    return CDIRECTIONS[direction];
  }


  /// string output
  std::string to_str(uLocation loc)
  {
    std::ostringstream str;
    str << '(' << std::setw(2) << get_row(loc) << ',' << std::setw(2) << get_col(loc) << ')';
    return str.str();
  }


  /// string output
  std::string to_str(uLocation from, uLocation to)
  {
    std::ostringstream str;
    str << '(' << std::setw(2) << get_row(from) << ',' << std::setw(2) << get_col(from) << ')'
	<< " -> " << '(' << std::setw(2) << get_row(to) << ',' << std::setw(2) << get_col(to) << ") [" 
	<< direction_name(getDirection(from,to)) << ']';
    return str.str();
  }



};


#endif /* _TORUS_HH_ */

